// 归并排序

function mergeSort(arr){
    _mergeSort(arr, 0, arr.length - 1)
}

// 将arr[l,...,mid]和arr[mid+1,...,r]归并
function _merge(arr, l, r, mid) {
    let copyArr = [];
    for (let i = l; i <= r; i++) {
        copyArr[i - l] = arr[i]
    }

    let i = l, j = mid + 1
    for (let k = l; k <= r; k++) {
        if (i > mid) {
            arr[k] = copyArr[j - l]
            j++
        } else if (j > r) {
            arr[k] = copyArr[i - l];
            i++
        } else if(copyArr[i - l] > copyArr[j - l]) {
            arr[k] = copyArr[j - l];
            j ++
        } else {
            arr[k] = copyArr[i - l];
            i ++
        }
    }
}

function _mergeSort(arr, l, r) {

    // if (l >= r) return;
    if (r - l <= 10) {   // 归并优化2：插入排序对其的优化
        insertSort(arr, l ,r)
        return
    }

    let mid = Math.floor((r + l)/2);
    _mergeSort(arr, l, mid)
    _mergeSort(arr, mid + 1, r)

    if (arr[mid] > arr[mid + 1]) {  // 归并优化1：对有序数据优化
        _merge(arr, l, r, mid)
    }
}

// 对arr数组[l,...,r]的数据进行插入排序
function insertSort(arr, l ,r) {
    for (let i = l + 1; i <= r; i++) {
        let variable = arr[i], j = i;
        for (;j > l && arr[j - 1] > variable; j--) {
            arr[j] = arr[j - 1]
        }
        arr[j] = variable
    }
}

let a = [1,5,8,7,4,6,9,8,2,1,8,5,4,1,3,9,7,4,6,84,15,4,521,475,1,7485,1,74,3,5,4,2,4,7]
mergeSort(a)
console.log(a)

// 自底向上的归并排序
function mergeSortBottomUp (arr) {
    let len = arr.length
    for (let sz = 1; sz <= len; sz+= sz) {
        for (let i = 0; i + sz< len; i += sz + sz) {
            // 对arr[i,...,i+sz-1]和arr[i+sz,....,1+2*sz-1]进行归并
            _merge(arr, i, Math.min(sz + sz + i - 1, len-1), sz + i - 1)
        }
    }
}

let b = [1,5,8,7,4,6,9,8,2,1,8,5,4,1,3,9,7,4,6,84,15,4,521,475,1,7485,1,74,3,5,4,2,4,7]
mergeSortBottomUp(b)
console.log(b)